import java.time.Period;
import java.util.zip.CRC32;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-20
 * Time: 17:35
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    /**
     *  获得链表长度
     * @param head
     * @return
     */
    public int getLength (ListNode head){
        ListNode cur = head;
        int len = 0;
        while (cur != null){
            len ++ ;
            cur = cur.next;
        }
        return len;
    }

    /**
     *  自底向上, 空间复杂度为 O(1)
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        int len = getLength(head);
        // 多开辟一个头节点, 方便合并时往后面接
        ListNode nHead = new ListNode(-1);
        nHead.next = head;
        for (int i = 1; i < len; i *= 2) {
            // 每次从头合并时, 头节点都会变, 但是因为有一个哨兵位节点, 所以头节点一定在哨兵位节点后面
            ListNode prev = nHead;
            // 每次重新合并都要重新开始
            ListNode cur = nHead.next;
            while (cur != null){
                ListNode head1 = cur;  // 记录第一条链开头
                ListNode head2 = null; // 记录第二条链开头
                // 找第一个链表
                for (int j = 1; j < i && cur != null; j++) {
                    cur = cur.next;
                }
                if (cur != null){
                    head2 = cur.next;
                    cur.next = null;
                }
                cur = head2;
                // 开始找第二条链
                for (int j = 1; j < i && cur != null && cur.next != null; j++) {
                    cur = cur.next;
                }
                if (cur != null){
                    ListNode next = cur.next;
                    cur.next = null;
                    cur = next;
                }
                // 合并两个链表
                prev.next = merge(head1, head2);
                // prev 要始终记录前面已经合并的链表的尾部
                while (prev.next != null){
                    prev = prev.next;
                }
            }
        }
        // nHead 后面记录的始终是最新的头节点
        return nHead.next;
    }

    /**
     *  合并两个链表
     * @param head1
     * @param head2
     * @return
     */
    private ListNode merge(ListNode head1, ListNode head2) {
        // 同样开辟一个头节点, 方便连接
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while (head1 != null && head2 != null){
            if (head1.val < head2.val){
                tail.next = head1;
                head1 = head1.next;
            }else{
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if (head1 != null){
            tail.next = head1;
        }
        if (head2 != null){
            tail.next = head2;
        }
        return head.next;
    }


    /**
     *  自顶向下 空间复杂度为 logn
     * @param head
     * @return
     */
    public ListNode getMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        if (prev != null){
            prev.next = null;
        }
        return slow;
    }

    /**
     *  递归合并两个链表
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        // 只有一个节点或者没有节点, 不用合并, 直接返回
        if (head == null || head.next == null){
            return head;
        }
        // 得到中间节点
        ListNode mid = getMid(head);
        // 将链表分为两部分, 先使两个链表都有序
        head = sortList(head);
        mid = sortList(mid);
        // 再合并两个有序链表
        // 多定义了一个头节点
        ListNode nHead = new ListNode(-1);
        ListNode cur = nHead;
        while (head != null && mid != null){
            if (head.val < mid.val){
                cur.next = head;
                head = head.next;
            }else {
                cur.next = mid;
                mid = mid.next;
            }
            cur = cur.next;
        }
        if (head != null){
            cur.next = head;
        }
        if (mid != null){
            cur.next = mid;
        }
        return nHead.next;
    }
}